home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gxht.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  16.5 KB  |  531 lines
  1. /* Copyright (C) 1989, 1995, 1996, 1997, 1998, 1999 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gxht.c,v 1.2 2000/09/19 19:00:37 lpd Exp $ */
  20. /* Halftone rendering for imaging library */
  21. #include "memory_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gsstruct.h"
  25. #include "gsbitops.h"
  26. #include "gsutil.h"        /* for gs_next_ids */
  27. #include "gxdcolor.h"
  28. #include "gxfixed.h"
  29. #include "gxdevice.h"        /* for gzht.h */
  30. #include "gxistate.h"
  31. #include "gzht.h"
  32.  
  33. /* Define the sizes of the halftone cache. */
  34. #define max_cached_tiles_HUGE 5000    /* not used */
  35. #define max_ht_bits_HUGE 1000000    /* not used */
  36. #define max_cached_tiles_LARGE 577
  37. #define max_ht_bits_LARGE 100000
  38. #define max_cached_tiles_SMALL 25
  39. #define max_ht_bits_SMALL 1000
  40.  
  41. /* Define the binary halftone device color type. */
  42. /* The type descriptor must be public for Pattern types. */
  43. gs_public_st_composite(st_dc_ht_binary, gx_device_color, "dc_ht_binary",
  44.                dc_ht_binary_enum_ptrs, dc_ht_binary_reloc_ptrs);
  45. private dev_color_proc_load(gx_dc_ht_binary_load);
  46. private dev_color_proc_fill_rectangle(gx_dc_ht_binary_fill_rectangle);
  47. private dev_color_proc_equal(gx_dc_ht_binary_equal);
  48. const gx_device_color_type_t
  49.       gx_dc_type_data_ht_binary =
  50. {&st_dc_ht_binary,
  51.  gx_dc_ht_binary_load, gx_dc_ht_binary_fill_rectangle,
  52.  gx_dc_default_fill_masked, gx_dc_ht_binary_equal
  53. };
  54.  
  55. #undef gx_dc_type_ht_binary
  56. const gx_device_color_type_t *const gx_dc_type_ht_binary =
  57. &gx_dc_type_data_ht_binary;
  58.  
  59. #define gx_dc_type_ht_binary (&gx_dc_type_data_ht_binary)
  60. /* GC procedures */
  61. private 
  62. ENUM_PTRS_WITH(dc_ht_binary_enum_ptrs, gx_device_color *cptr) return 0;
  63. ENUM_PTR(0, gx_device_color, colors.binary.b_ht);
  64. case 1:
  65. {
  66.     gx_ht_tile *tile = cptr->colors.binary.b_tile;
  67.  
  68.     ENUM_RETURN(tile - tile->index);
  69. }
  70. ENUM_PTRS_END
  71. private RELOC_PTRS_WITH(dc_ht_binary_reloc_ptrs, gx_device_color *cptr)
  72. {
  73.     uint index = cptr->colors.binary.b_tile->index;
  74.  
  75.     RELOC_PTR(gx_device_color, colors.binary.b_ht);
  76.     RELOC_TYPED_OFFSET_PTR(gx_device_color, colors.binary.b_tile, index);
  77. }
  78. RELOC_PTRS_END
  79. #undef cptr
  80.  
  81. /* Other GC procedures */
  82. private_st_ht_tiles();
  83. private 
  84. ENUM_PTRS_BEGIN_PROC(ht_tiles_enum_ptrs)
  85. {
  86.     return 0;
  87. }
  88. ENUM_PTRS_END_PROC
  89. private RELOC_PTRS_BEGIN(ht_tiles_reloc_ptrs)
  90. {
  91.     /* Reset the bitmap pointers in the tiles. */
  92.     /* We know the first tile points to the base of the bits. */
  93.     gx_ht_tile *ht_tiles = vptr;
  94.     byte *bits = ht_tiles->tiles.data;
  95.     uint diff;
  96.  
  97.     if (bits == 0)
  98.     return;
  99.     RELOC_VAR(bits);
  100.     if (size == size_of(gx_ht_tile)) {    /* only 1 tile */
  101.     ht_tiles->tiles.data = bits;
  102.     return;
  103.     }
  104.     diff = ht_tiles[1].tiles.data - ht_tiles[0].tiles.data;
  105.     for (; size; ht_tiles++, size -= size_of(gx_ht_tile), bits += diff) {
  106.     ht_tiles->tiles.data = bits;
  107.     }
  108. }
  109. RELOC_PTRS_END
  110. private_st_ht_cache();
  111.  
  112. /* Return the default sizes of the halftone cache. */
  113. uint
  114. gx_ht_cache_default_tiles(void)
  115. {
  116. #if arch_small_memory
  117.     return max_cached_tiles_SMALL;
  118. #else
  119.     return (gs_debug_c('.') ? max_cached_tiles_SMALL :
  120.         max_cached_tiles_LARGE);
  121. #endif
  122. }
  123. uint
  124. gx_ht_cache_default_bits(void)
  125. {
  126. #if arch_small_memory
  127.     return max_ht_bits_SMALL;
  128. #else
  129.     return (gs_debug_c('.') ? max_ht_bits_SMALL :
  130.         max_ht_bits_LARGE);
  131. #endif
  132. }
  133.  
  134. /* Allocate a halftone cache. */
  135. gx_ht_cache *
  136. gx_ht_alloc_cache(gs_memory_t * mem, uint max_tiles, uint max_bits)
  137. {
  138.     gx_ht_cache *pcache =
  139.     gs_alloc_struct(mem, gx_ht_cache, &st_ht_cache,
  140.             "alloc_ht_cache(struct)");
  141.     byte *tbits =
  142.     gs_alloc_bytes(mem, max_bits, "alloc_ht_cache(bits)");
  143.     gx_ht_tile *ht_tiles =
  144.     gs_alloc_struct_array(mem, max_tiles, gx_ht_tile, &st_ht_tiles,
  145.                   "alloc_ht_cache(ht_tiles)");
  146.  
  147.     if (pcache == 0 || tbits == 0 || ht_tiles == 0) {
  148.     gs_free_object(mem, ht_tiles, "alloc_ht_cache(ht_tiles)");
  149.     gs_free_object(mem, tbits, "alloc_ht_cache(bits)");
  150.     gs_free_object(mem, pcache, "alloc_ht_cache(struct)");
  151.     return 0;
  152.     }
  153.     pcache->bits = tbits;
  154.     pcache->bits_size = max_bits;
  155.     pcache->ht_tiles = ht_tiles;
  156.     pcache->num_tiles = max_tiles;
  157.     pcache->order.cache = pcache;
  158.     pcache->order.transfer = 0;
  159.     gx_ht_clear_cache(pcache);
  160.     return pcache;
  161. }
  162.  
  163. /* Free a halftone cache. */
  164. void
  165. gx_ht_free_cache(gs_memory_t * mem, gx_ht_cache * pcache)
  166. {
  167.     gs_free_object(mem, pcache->ht_tiles, "free_ht_cache(ht_tiles)");
  168.     gs_free_object(mem, pcache->bits, "free_ht_cache(bits)");
  169.     gs_free_object(mem, pcache, "free_ht_cache(struct)");
  170. }
  171.  
  172. /* Make the cache order current, and return whether */
  173. /* there is room for all possible tiles in the cache. */
  174. bool
  175. gx_check_tile_cache(const gs_imager_state * pis)
  176. {
  177.     const gx_ht_order *porder = &pis->dev_ht->order;
  178.     gx_ht_cache *pcache = pis->ht_cache;
  179.  
  180.     if (pcache == 0 || pis->dev_ht == 0)
  181.     return false;        /* no halftone or cache */
  182.     if (pcache->order.bit_data != porder->bit_data)
  183.     gx_ht_init_cache(pcache, porder);
  184.     if (pcache->tiles_fit >= 0)
  185.     return (bool)pcache->tiles_fit;
  186.     {
  187.     bool fit = false;
  188.     int bits_per_level;
  189.  
  190.     if (pcache->num_cached < porder->num_levels)
  191.         DO_NOTHING;
  192.     else if (pcache->levels_per_tile == 1)
  193.         fit = true;
  194.     /*
  195.      * All the tiles fit iff bits and levels are exactly N-for-1, where
  196.      * N is a multiple of levels_per_tile.
  197.      */
  198.     else if (porder->num_bits % porder->num_levels == 0 &&
  199.          (bits_per_level = porder->num_bits / porder->num_levels) %
  200.            pcache->levels_per_tile == 0) {
  201.         /* Check the N-for-1 property. */
  202.         const uint *level = porder->levels;
  203.         int i = porder->num_levels, j = 0;
  204.  
  205.         for (; i > 0; --i, j += bits_per_level, ++level)
  206.         if (*level != j)
  207.             break;
  208.         fit = i == 0;
  209.     }
  210.     pcache->tiles_fit = (int)fit;
  211.     return fit;
  212.     }
  213. }
  214.  
  215. /*
  216.  * Determine whether a given (width, y, height) might fit into a single
  217.  * (non-strip) tile. If so, return the byte offset of the appropriate row
  218.  * from the beginning of the tile, and set *ppx to the x phase offset
  219.  * within the tile; if not, return -1.
  220.  */
  221. int
  222. gx_check_tile_size(const gs_imager_state * pis, int w, int y, int h,
  223.            gs_color_select_t select, int *ppx)
  224. {
  225.     int tsy;
  226.     const gx_strip_bitmap *ptile0;
  227.  
  228.     if (pis->ht_cache == 0)
  229.     return -1;        /* no halftone cache */
  230.     ptile0 = &pis->ht_cache->ht_tiles[0].tiles;        /* a typical tile */
  231.     if (h > ptile0->rep_height || w > ptile0->rep_width ||
  232.     ptile0->shift != 0
  233.     )
  234.     return -1;
  235.     tsy = (y + imod(-pis->screen_phase[select].y, ptile0->rep_height)) %
  236.     ptile0->rep_height;
  237.     if (tsy + h > ptile0->size.y)
  238.     return -1;
  239.     /* Tile fits in Y, might fit in X. */
  240.     *ppx = imod(-pis->screen_phase[select].x, ptile0->rep_width);
  241.     return tsy * ptile0->raster;
  242. }
  243.  
  244. /* Render a given level into a halftone cache. */
  245. private int render_ht(P4(gx_ht_tile *, int, const gx_ht_order *,
  246.              gx_bitmap_id));
  247. private gx_ht_tile *
  248. gx_render_ht_default(gx_ht_cache * pcache, int b_level)
  249. {
  250.     const gx_ht_order *porder = &pcache->order;
  251.     int level = porder->levels[b_level];
  252.     gx_ht_tile *bt = &pcache->ht_tiles[level / pcache->levels_per_tile];
  253.  
  254.     if (bt->level != level) {
  255.     int code = render_ht(bt, level, porder, pcache->base_id + b_level);
  256.  
  257.     if (code < 0)
  258.         return 0;
  259.     }
  260.     return bt;
  261. }
  262. /* Faster code if num_tiles == 1. */
  263. private gx_ht_tile *
  264. gx_render_ht_1_tile(gx_ht_cache * pcache, int b_level)
  265. {
  266.     const gx_ht_order *porder = &pcache->order;
  267.     int level = porder->levels[b_level];
  268.     gx_ht_tile *bt = &pcache->ht_tiles[0];
  269.  
  270.     if (bt->level != level) {
  271.     int code = render_ht(bt, level, porder, pcache->base_id + b_level);
  272.  
  273.     if (code < 0)
  274.         return 0;
  275.     }
  276.     return bt;
  277. }
  278. /* Faster code if levels_per_tile == 1. */
  279. private gx_ht_tile *
  280. gx_render_ht_1_level(gx_ht_cache * pcache, int b_level)
  281. {
  282.     const gx_ht_order *porder = &pcache->order;
  283.     int level = porder->levels[b_level];
  284.     gx_ht_tile *bt = &pcache->ht_tiles[level];
  285.  
  286.     if (bt->level != level) {
  287.     int code = render_ht(bt, level, porder, pcache->base_id + b_level);
  288.  
  289.     if (code < 0)
  290.         return 0;
  291.     }
  292.     return bt;
  293. }
  294.  
  295. /* Load the device color into the halftone cache if needed. */
  296. private int
  297. gx_dc_ht_binary_load(gx_device_color * pdevc, const gs_imager_state * pis,
  298.              gx_device * dev, gs_color_select_t select)
  299. {
  300.     int component_index = pdevc->colors.binary.b_index;
  301.     const gx_ht_order *porder =
  302.     (component_index < 0 ?
  303.      &pdevc->colors.binary.b_ht->order :
  304.      &pdevc->colors.binary.b_ht->components[component_index].corder);
  305.     gx_ht_cache *pcache =
  306.     (porder->cache == 0 ? pis->ht_cache : porder->cache);
  307.  
  308.     if (pcache->order.bit_data != porder->bit_data)
  309.     gx_ht_init_cache(pcache, porder);
  310.     /* Expand gx_render_ht inline for speed. */
  311.     {
  312.     int b_level = pdevc->colors.binary.b_level;
  313.     int level = porder->levels[b_level];
  314.     gx_ht_tile *bt = &pcache->ht_tiles[level / pcache->levels_per_tile];
  315.  
  316.     if (bt->level != level) {
  317.         int code = render_ht(bt, level, porder,
  318.                  pcache->base_id + b_level);
  319.  
  320.         if (code < 0)
  321.         return_error(gs_error_Fatal);
  322.     }
  323.     pdevc->colors.binary.b_tile = bt;
  324.     }
  325.     return 0;
  326. }
  327.  
  328. /* Fill a rectangle with a binary halftone. */
  329. /* Note that we treat this as "texture" for RasterOp. */
  330. private int
  331. gx_dc_ht_binary_fill_rectangle(const gx_device_color * pdevc, int x, int y,
  332.           int w, int h, gx_device * dev, gs_logical_operation_t lop,
  333.                    const gx_rop_source_t * source)
  334. {
  335.     gx_rop_source_t no_source;
  336.  
  337.     /*
  338.      * Observation of H-P devices and documentation yields confusing
  339.      * evidence about whether white pixels in halftones are always
  340.      * opaque.  It appears that for black-and-white devices, these
  341.      * pixels are *not* opaque.
  342.      */
  343.     if (dev->color_info.depth > 1)
  344.     lop &= ~lop_T_transparent;
  345.     if (source == NULL && lop_no_S_is_T(lop))
  346.     return (*dev_proc(dev, strip_tile_rectangle)) (dev,
  347.                     &pdevc->colors.binary.b_tile->tiles,
  348.                   x, y, w, h, pdevc->colors.binary.color[0],
  349.                           pdevc->colors.binary.color[1],
  350.                         pdevc->phase.x, pdevc->phase.y);
  351.     /* Adjust the logical operation per transparent colors. */
  352.     if (pdevc->colors.binary.color[0] == gx_no_color_index)
  353.     lop = rop3_use_D_when_T_0(lop);
  354.     if (pdevc->colors.binary.color[1] == gx_no_color_index)
  355.     lop = rop3_use_D_when_T_1(lop);
  356.     if (source == NULL)
  357.     set_rop_no_source(source, no_source, dev);
  358.     return (*dev_proc(dev, strip_copy_rop)) (dev, source->sdata,
  359.                    source->sourcex, source->sraster, source->id,
  360.                  (source->use_scolors ? source->scolors : NULL),
  361.                     &pdevc->colors.binary.b_tile->tiles,
  362.                          pdevc->colors.binary.color,
  363.                  x, y, w, h, pdevc->phase.x, pdevc->phase.y,
  364.                          lop);
  365. }
  366.  
  367. /* Compare two binary halftones for equality. */
  368. private bool
  369. gx_dc_ht_binary_equal(const gx_device_color * pdevc1,
  370.               const gx_device_color * pdevc2)
  371. {
  372.     return pdevc2->type == pdevc1->type &&
  373.     pdevc1->phase.x == pdevc2->phase.x &&
  374.     pdevc1->phase.y == pdevc2->phase.y &&
  375.     gx_dc_binary_color0(pdevc1) == gx_dc_binary_color0(pdevc2) &&
  376.     gx_dc_binary_color1(pdevc1) == gx_dc_binary_color1(pdevc2) &&
  377.     pdevc1->colors.binary.b_level == pdevc2->colors.binary.b_level;
  378. }
  379.  
  380. /* Initialize the tile cache for a given screen. */
  381. /* Cache as many different levels as will fit. */
  382. void
  383. gx_ht_init_cache(gx_ht_cache * pcache, const gx_ht_order * porder)
  384. {
  385.     uint width = porder->width;
  386.     uint height = porder->height;
  387.     uint size = width * height + 1;
  388.     int width_unit =
  389.     (width <= ht_mask_bits / 2 ? ht_mask_bits / width * width :
  390.      width);
  391.     int height_unit = height;
  392.     uint raster = porder->raster;
  393.     uint tile_bytes = raster * height;
  394.     uint shift = porder->shift;
  395.     int num_cached;
  396.     int i;
  397.     byte *tbits = pcache->bits;
  398.  
  399.     /* Non-monotonic halftones may have more bits than size. */
  400.     if (porder->num_bits >= size)
  401.     size = porder->num_bits + 1;
  402.     /* Make sure num_cached is within bounds */
  403.     num_cached = pcache->bits_size / tile_bytes;
  404.     if (num_cached > size)
  405.     num_cached = size;
  406.     if (num_cached > pcache->num_tiles)
  407.     num_cached = pcache->num_tiles;
  408.     if (num_cached == size &&
  409.     tile_bytes * num_cached <= pcache->bits_size / 2
  410.     ) {
  411.     /*
  412.      * We can afford to replicate every tile in the cache,
  413.      * which will reduce breakage when tiling.  Since
  414.      * horizontal breakage is more expensive than vertical,
  415.      * and since wide shallow fills are more common than
  416.      * narrow deep fills, we replicate the tile horizontally.
  417.      * We do have to be careful not to replicate the tile
  418.      * to an absurdly large size, however.
  419.      */
  420.     uint rep_raster =
  421.     ((pcache->bits_size / num_cached) / height) &
  422.     ~(align_bitmap_mod - 1);
  423.     uint rep_count = rep_raster * 8 / width;
  424.  
  425.     /*
  426.      * There's no real value in replicating the tile
  427.      * beyond the point where the byte width of the replicated
  428.      * tile is a multiple of a long.
  429.      */
  430.     if (rep_count > sizeof(ulong) * 8)
  431.         rep_count = sizeof(ulong) * 8;
  432.     width_unit = width * rep_count;
  433.     raster = bitmap_raster(width_unit);
  434.     tile_bytes = raster * height;
  435.     }
  436.     pcache->base_id = gs_next_ids(porder->num_levels + 1);
  437.     pcache->order = *porder;
  438.     /* The transfer function is irrelevant, and might become dangling. */
  439.     pcache->order.transfer = 0;
  440.     pcache->num_cached = num_cached;
  441.     pcache->levels_per_tile = (size + num_cached - 1) / num_cached;
  442.     pcache->tiles_fit = -1;
  443.     memset(tbits, 0, pcache->bits_size);
  444.     for (i = 0; i < num_cached; i++, tbits += tile_bytes) {
  445.     register gx_ht_tile *bt = &pcache->ht_tiles[i];
  446.  
  447.     bt->level = 0;
  448.     bt->index = i;
  449.     bt->tiles.data = tbits;
  450.     bt->tiles.raster = raster;
  451.     bt->tiles.size.x = width_unit;
  452.     bt->tiles.size.y = height_unit;
  453.     bt->tiles.rep_width = width;
  454.     bt->tiles.rep_height = height;
  455.     bt->tiles.shift = bt->tiles.rep_shift = shift;
  456.     }
  457.     pcache->render_ht =
  458.     (pcache->num_tiles == 1 ? gx_render_ht_1_tile :
  459.      pcache->levels_per_tile == 1 ? gx_render_ht_1_level :
  460.      gx_render_ht_default);
  461. }
  462.  
  463. /*
  464.  * Compute and save the rendering of a given gray level
  465.  * with the current halftone.  The cache holds multiple tiles,
  466.  * where each tile covers a range of possible levels.
  467.  * We adjust the tile whose range includes the desired level incrementally;
  468.  * this saves a lot of time for the average image, where gray levels
  469.  * don't change abruptly.  Note that the "level" is the number of bits,
  470.  * not the index in the levels vector.
  471.  */
  472. private int
  473. render_ht(gx_ht_tile * pbt, int level /* [1..num_bits-1] */ ,
  474.       const gx_ht_order * porder, gx_bitmap_id new_id)
  475. {
  476.     byte *data = pbt->tiles.data;
  477.     int code;
  478.  
  479.     if_debug7('H', "[H]Halftone cache slot 0x%lx: old=%d, new=%d, w=%d(%d), h=%d(%d):\n",
  480.           (ulong) data, pbt->level, level,
  481.           pbt->tiles.size.x, porder->width,
  482.           pbt->tiles.size.y, porder->num_bits / porder->width);
  483. #ifdef DEBUG
  484.     if (level < 0 || level > porder->num_bits) {
  485.     lprintf3("Error in render_ht: level=%d, old level=%d, num_bits=%d\n",
  486.          level, pbt->level, porder->num_bits);
  487.     return_error(gs_error_Fatal);
  488.     }
  489. #endif
  490.     code = porder->procs->render(pbt, level, porder);
  491.     if (code < 0)
  492.     return code;
  493.     pbt->level = level;
  494.     pbt->tiles.id = new_id;
  495.     /*
  496.      * Check whether we want to replicate the tile in the cache.
  497.      * Since we only do this when all the renderings will fit
  498.      * in the cache, we only do it once per level, and it doesn't
  499.      * have to be very efficient.
  500.      */
  501.     /****** TEST IS WRONG if width > rep_width but tile.raster ==
  502.      ****** order raster.
  503.      ******/
  504.     if (pbt->tiles.raster > porder->raster)
  505.     bits_replicate_horizontally(data, pbt->tiles.rep_width,
  506.                     pbt->tiles.rep_height, porder->raster,
  507.                     pbt->tiles.size.x, pbt->tiles.raster);
  508.     if (pbt->tiles.size.y > pbt->tiles.rep_height &&
  509.     pbt->tiles.shift == 0
  510.     )
  511.     bits_replicate_vertically(data, pbt->tiles.rep_height,
  512.                   pbt->tiles.raster, pbt->tiles.size.y);
  513. #ifdef DEBUG
  514.     if (gs_debug_c('H')) {
  515.     const byte *p = pbt->tiles.data;
  516.     int wb = pbt->tiles.raster;
  517.     const byte *ptr = p + wb * pbt->tiles.size.y;
  518.  
  519.     while (p < ptr) {
  520.         dprintf8(" %d%d%d%d%d%d%d%d",
  521.              *p >> 7, (*p >> 6) & 1, (*p >> 5) & 1,
  522.              (*p >> 4) & 1, (*p >> 3) & 1, (*p >> 2) & 1,
  523.              (*p >> 1) & 1, *p & 1);
  524.         if ((++p - data) % wb == 0)
  525.         dputc('\n');
  526.     }
  527.     }
  528. #endif
  529.     return 0;
  530. }
  531.